﻿#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<stdlib.h>

//OR140 数列
// https://www.nowcoder.com/practice/1843c3b052984e3f98c68935ea3c0d79?tpId=182&&tqId=34866&rp=1&ru=/ta/exam-all&qru=/ta/exam-all/question-ranking
//某种特殊的数列a1, a2, a3, ...的定义如下：a1 = 1, a2 = 2, ..., an = 2 * an − 1 + an - 2 (n > 2)。
//给出任意一个正整数k，求该数列的第k项模以32767的结果是多少？

int main() {
    int n = 0;
    int num = 0;
    int* a = (int*)malloc(sizeof(int) * 1000000);
    a[0] = 1;
    a[1] = 2;
    scanf("%d", &n);
    for (int i = 2; i < 1000000; i++)
    {
        a[i] = (2 * a[i - 1] + a[i - 2]) % 32767; //需先取模再存入，否则可能会溢出
    }
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &num);
        printf("%d\n", a[num - 1]);
    }
    return 0;
}